/*
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.rules.als;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

import com.onegravity.sudoku.solver.HintResource;
import com.onegravity.sudoku.solver.R;
import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.IndirectHint;
import com.onegravity.sudoku.solver.core.IndirectHintProducer;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.data.NeighborManager;
import com.onegravity.sudoku.solver.data.Region;
import com.onegravity.sudoku.solver.util.BitSetFactory;
import com.onegravity.sudoku.solver.util.Permutations;

/**
 * ALS Producer supports:
 * ALS-XZ
 * ALS-XY-Wing
 * not yet: ALS-XY-Chain
 * @author Emanuel Moecklin
 */
public class ALSProducer implements IndirectHintProducer {
	
	private boolean mUseALSXZ;
	private boolean mUseALSXYWing;
	
	public ALSProducer(boolean useALSXZ, boolean useALSXYWing) {
		mUseALSXZ = useALSXZ;
		mUseALSXYWing = useALSXYWing;
	}
	
	@Override
    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
		if (!mUseALSXZ && !mUseALSXYWing) return; 
		
		// (1) compute the neighbors for this grid as CellSets
    	NumberSet[] neighborSets = getNeighbors(grid);

    	// (2) collect all ALS in this grid
    	Set<ALS> allALS = findALSes(grid);

    	// (3) collect all common candidates (including RCCs) for all pairs of ALSs
    	Collection<CommonCandidates> commonCandidatesList = findCommonCandidates(allALS, neighborSets);
		
    	// (4) find all ALS-XZs
		if (mUseALSXZ) findALSXZ(commonCandidatesList, accu);
    	
		// (5) find all ALS-XY-Wings
    	if (mUseALSXYWing) findALSXYWing(allALS, commonCandidatesList, accu);

    	// (6) find all ALS-XY-Chains
		//findALSXYChain(allALS, commonCandidatesList, accu);
    }
	
	// ****************************************** ALS-XZ Methods *******************************************

	/*
	 * Find all ALS-XZ
	 * A -> rcc -> B -> cc -> A
	 */
	private void findALSXZ(Collection<CommonCandidates> commonCandidatesList, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
		for (CommonCandidates ccs:commonCandidatesList) {
            if (Thread.interrupted()) throw new InterruptedException();
			if (!ccs.hasRCCs()) continue;
			NumberSet rcc = ccs.getRestrictedCommonCandidates();
			for (int x=1; x<=9; x++) {
				if (rcc.contains(x)) {
					NumberSet cc = ccs.getCommonCandidates();
					// check if there is a z value 
					for (int z=1; z<=9; z++) {
						if (z!=x && cc.contains(z)) {
							ALS als1 = ccs.getALS1();
							ALS als2 = ccs.getALS2();
							Collection<Cell> als1Cells4Value = als1.getCells(z);
							Collection<Cell> als2Cells4Value = als2.getCells(z);
							@SuppressWarnings("unchecked")
							Map<Cell,BitSet> removablePotentials = findRemovablePotentials(z, als1Cells4Value, als2Cells4Value);
							IndirectHint hint = new ALSXZHint(ccs, x, z, removablePotentials);
							if (hint.isWorth()) accu.add(hint);		// we found an ALS-XZ
						}
					}
				}
			}
		}
	}
	
	// ****************************************** ALS-XY-Wing Methods *******************************************

	/**
	 * Find all ALS-XY-Wings
	 * A -> rcc -> B -> rcc -> C -> cc -> A
	 * @throws InterruptedException 
	 */
	private void findALSXYWing(Set<ALS> allALS, Collection<CommonCandidates> commonCandidatesList, HintsAccumulator accu)
								 throws StopHintProductionException, InterruptedException {
		// (1) find ALS with two unique RCCs (ALS B)
		for (ALS alsB:allALS) {
            if (Thread.interrupted()) throw new InterruptedException();
			List<CommonCandidates> ccs = alsB.getCommonCandidates();
			// (1.1) ALS B needs at least two common candidates
			int nrOfCC = ccs.size();
			if (nrOfCC<2) continue;
			// (1.2) let's find two common candidates with different RCCs
			for (int i=0; i<nrOfCC; i++) {
				for (int t=i+1; t<nrOfCC; t++) {
	                CommonCandidates cc1 = ccs.get(i);
	                if (!cc1.hasRCCs()) continue;
	                CommonCandidates cc2 = ccs.get(t); 
	                if (!cc2.hasRCCs()) continue;
	                NumberSet rcc1 = cc1.getRestrictedCommonCandidates();
	                NumberSet rcc2 = cc2.getRestrictedCommonCandidates();
	                for (int x=1; x<=9; x++) {
	                	if (rcc1.contains(x)) {
	                        for (int y=1; y<=9; y++) {
	                        	// rccs must be different and we also need to eliminate combinations we already had before (xy <--> yx)
	                        	if (y!=x && rcc2.contains(y) && (y>x || !rcc1.contains(y) || !rcc2.contains(x))) {
	                        		// (2) found an ALS with two unique RCC, now check if it's an ALSXYWing
	                        		check4ALSXYWing(cc1.getOtherALS(alsB), alsB, cc2.getOtherALS(alsB), x, y, accu);
	                        	}
	                        }
	                	}
	                }
				}
			}
		}
	}
	
	private void check4ALSXYWing(ALS alsA, ALS alsB, ALS alsC, int x, int y, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
        if (Thread.interrupted()) throw new InterruptedException();
		Collection<Integer> zValues = getCommonCandidates(alsA, alsC, BitSetFactory.createTwoElement(x, y));
		if (zValues!=null) {
			for (Integer z:zValues) {
				// we found an ALS-XY-Wing, now let's check if there are any candidates to eliminate
				Collection<Cell> als1Cells4Value = alsA.getCells(z);
				Collection<Cell> als2Cells4Value = alsC.getCells(z);
				@SuppressWarnings("unchecked")
				Map<Cell,BitSet> removablePotentials = findRemovablePotentials(z, als1Cells4Value, als2Cells4Value);
				IndirectHint hint = new ALSXYWingHint(alsA, alsB, alsC, x, y, z, removablePotentials);
				if (hint.isWorth()) accu.add(hint);		// we found an ALS-XY-Wing
			}
		}
	}
	
	// ****************************************** ALS-XY-Chain Methods *******************************************

	/**
	 * Find all ALS-XY-Chains
	 * A -> rcc -> B -> rcc -> C -> rcc -> D ... N -> cc -> A
	 * @throws InterruptedException 
	 * @throws StopHintProductionException 
	 */
	@SuppressWarnings("unused")
	private void findALSXYChain(Set<ALS> allALS, Collection<CommonCandidates> commonCandidatesList, HintsAccumulator accu) throws InterruptedException, StopHintProductionException {

		BitSet usedCandidates = new BitSet();
		
		// Find all ALS Chains
		for (ALS startALS:allALS) {
            if (Thread.interrupted()) throw new InterruptedException();
			LinkedList<ALS> alsChain = new LinkedList<ALS>();
			alsChain.add(startALS);

			if (getALSChain(alsChain, usedCandidates, -1)) {
				if (alsChain.size()==2) {
					// found an ALS-XZ
				}
				else if (alsChain.size()==3) {
					// found an ALS-XY-Wing
					/*Logger.e(getClass().getSimpleName(), "-----------------------------------------------------------");
					Logger.e(getClass().getSimpleName(), "ALS-XY-Wing found");
					for (ALS als:alsChain) {
						Logger.e(getClass().getSimpleName(), als.toString());
					}*/
				}
				else if (alsChain.size()>=4) {
					/*Logger.e(getClass().getSimpleName(), "-----------------------------------------------------------");
					Logger.e(getClass().getSimpleName(), "ALS-XY-Chain found");
					for (ALS als:alsChain) {
						Logger.e(getClass().getSimpleName(), als.toString());
					}*/
				}
			}
		}
	}
	
	/**
	 * @return True if the chain could be closed
	 * @throws InterruptedException 
	 */
	private boolean getALSChain(LinkedList<ALS> alsChain, BitSet usedCandidates, int firstRCC) throws InterruptedException {
		if (Thread.interrupted()) throw new InterruptedException();
		
		// if the chain has at least four elements check for z values
		if (alsChain.size()==3) {
			ALS firstALS = alsChain.getFirst();
			ALS lastALS = alsChain.getLast();
			Collection<Integer> zValues = getCommonCandidates(firstALS, lastALS, usedCandidates);
			if (zValues!=null) {
				for (Integer z:zValues) {
					if (z==firstRCC || usedCandidates.get(z)) continue;
					Collection<Cell> firstALSCells4Value = firstALS.getCells(z);
					Collection<Cell> lastALSCells4Value = lastALS.getCells(z);
				    @SuppressWarnings("unchecked")
					Map<Cell,BitSet> removablePotentials = findRemovablePotentials(z, firstALSCells4Value, lastALSCells4Value);
				    if (!removablePotentials.isEmpty()) {
				    	return true;
				    }
				}
			}
		}
		if (alsChain.size()>3) return false;

		ALS startALS = alsChain.getLast();
		for (CommonCandidates startCCS:startALS.getCommonCandidates()) {
			if (!startCCS.hasRCCs()) continue;
			NumberSet startCC = startCCS.getRestrictedCommonCandidates();
			for (int rcc=1; rcc<=9; rcc++) {
				if (!usedCandidates.get(rcc) && startCC.contains(rcc)) {
					ALS nextALS = startCCS.getOtherALS(startALS);
					if (!alsChain.contains(nextALS)) {
						alsChain.add(nextALS);
						if (getALSChain(alsChain, BitSetFactory.createOneElement(rcc), (firstRCC==-1) ? rcc : firstRCC)) {
							// @TODO process the chain and then continue with recursion
							return true;
						}
						alsChain.remove(nextALS);
					}
				}
			}
		}
		return false;
	}
	
	// ****************************************** Common Methods *******************************************

	/**
	 * Collect all cell's neighbors as NumberSets (compared to the usually used int[])
	 */
	private NumberSet[] getNeighbors(Grid grid) {
    	NumberSet[] result = new NumberSet[81];
    	for (int index=0; index<81; index++) {
            NumberSet neighborSet = new NumberSet();
            for (int indexNeighbor : NeighborManager.getNeighbors(grid, index)) {
            	neighborSet.add(indexNeighbor);
            }
            result[index] = neighborSet;
    	}
    	return result;
	}
	
	/**
	 * Collects the ALSes for the grid
	 * @return A sorted set of ALS objects (sorted according to degree)
	 * @throws InterruptedException
	 */
	private Set<ALS> findALSes(Grid grid) throws InterruptedException {
		Set<ALS> result = new TreeSet<ALS>();
		int counter = 0; 
		BitSet unionPotentials = new BitSet();				// used locally only
		List<Cell> emptyCells = new ArrayList<Cell>();		// empty cells in a region
    	List<Cell> cells = new ArrayList<Cell>();			// ALS cells
		for (Class<? extends Region> regionType:grid.getRegionTypes()) {
			for (Region region:grid.getRegions(regionType)) {
                if (Thread.interrupted()) throw new InterruptedException();
				// (1.1) collect all empty cells for this region
				emptyCells.clear();
				for (Cell cell:region.getCellSet()) {
					if (cell.isEmpty()) emptyCells.add(cell);
				}
				// (1.2) find all ALS for all degrees (2-9) in this region (based on empty cells' list)
				int nrOfCells = emptyCells.size();
		    	for (int degree=2; degree<=9 && degree<=(nrOfCells+1); degree++) {
	                if (Thread.interrupted()) throw new InterruptedException();
	                Permutations perm = new Permutations(degree-1, nrOfCells);
	                while (perm.hasNext()) {
                        int[] indices = perm.nextBitNums();
                        // check for ALS on this permutation
                    	cells.clear();
                    	unionPotentials.clear();
                        for (int index:indices) {
                        	Cell cell = emptyCells.get(index);
                        	cells.add(cell);
                        	unionPotentials.or( cell.getPotentialValues() );
                    		if (unionPotentials.cardinality()>degree) break;
                        }
                    	if (unionPotentials.cardinality()==degree) {
                            ALS als = new ALS(grid, counter++, degree, new TreeSet<Cell>(cells), (BitSet) unionPotentials.clone(), region);
                            result.add(als);
                    	}
	                }
		    	}
			}
		}
		return result;
	}
	
	/**
	 * Collects all common candidates for a set of ALSs.
	 * The ALS objects are linked to the found CommonCandidates objects and the CommonCandidates are linked to the ALS objects
	 * (ALS -> 1:n -> CC -> 1:2 -> ALS) 
	 * @return A list of CommonCandidates objecs
	 * @throws InterruptedException
	 */
    private Collection<CommonCandidates> findCommonCandidates(Set<ALS> allALS, NumberSet[] neighborSets) throws InterruptedException {
		Collection<CommonCandidates> result = new ArrayList<CommonCandidates>();
    	Set<Integer> processedALSPairs = new HashSet<Integer>();
		for (ALS als1:allALS) {
			for (ALS als2:allALS) {
                if (Thread.interrupted()) throw new InterruptedException();
                // (0) we don't want to process the same ALS pair twice 
                Integer key = getUnqiueKey(als1, als2);
                if (processedALSPairs.contains(key)) continue;
                processedALSPairs.add(key);
                // (1) ALSs have common candidates but no common cells 
				if (als1.intersectsCandidates(als2) && !als1.intersectsCell(als2)) {
					CommonCandidates common = new CommonCandidates(als1, als2);
					int nrOfCommonCandidates = common.getNrOfCommonCandidates();
	                // (2) ALSs must have at least 1 common candidate
					if (nrOfCommonCandidates<1) continue;
					result.add(common);
					als1.addCommonCandidates(common);
					als2.addCommonCandidates(common);
					NumberSet commonCandidates = common.getCommonCandidates();
					for (int x=1; x<=9; x++) {
						if (!commonCandidates.contains(x)) continue;
						Collection<Cell> als1Cells4Value = als1.getCells(x);
						Collection<Cell> als2Cells4Value = als2.getCells(x);
						// (3) let's check if all cells with this value in ALS1 see all cells with this value in ALS2 
						boolean isRCC = true;
						outer:
						for (Cell als1Cell:als1Cells4Value) {
							NumberSet neighbors1 = neighborSets[als1Cell.getIndex()];
							for (Cell als2Cell:als2Cells4Value) {
								if (!neighbors1.contains(als2Cell.getIndex())) {
									isRCC = false;
									break outer;
								}
							}
						}
						if (isRCC) {
							common.addRestrictedCommonCandidate(x);
						}
					}
				}
			}
		}
		return result;
    }
	
    /**
     * Return the unique key for a given pair of ALSes
     * @param als1 The first ALS
     * @param als2 The second ALS
     * @return The unique key
     */
	private Integer getUnqiueKey(ALS als1, ALS als2) {
		int key1 = als1.getCounter();
		int key2 = als2.getCounter();
		return (key1<key2) ? (key1<<16)+key2 : (key2<<16)+key1;  
	}

	/**
	 * Find all common candidates for two given ALSes
	 * @param als1 The first ALS
	 * @param als2 The second ALS
	 * @param excludedCandidates exclude these common candidates from the resulting list
	 * @return
	 */
	private Collection<Integer> getCommonCandidates(ALS als1, ALS als2, BitSet excludedCandidates) {
		Collection<Integer> result = null;
		for (CommonCandidates commonCanidates:als1.getCommonCandidates()) {
			if (commonCanidates.getOtherALS(als1)==als2) {	// we use == because equals is rather slow and == does the job in this case
				NumberSet common = commonCanidates.getCommonCandidates();
				for (int z=1; z<=9; z++) {
					if (!excludedCandidates.get(z) && common.contains(z)) {
						if (result==null) result = new TreeSet<Integer>();
						result.add(z);
					}
				}
			}
		}
		return result;
	}
	
	/**
	 * Find all removable potentials for a given digit and a collection of cells.
	 * The resulting potentials are seen by all cells in the collection.
	 * @param value
	 * @param sourceCells
	 * @return
	 */
    private Map<Cell,BitSet> findRemovablePotentials(int value, Collection<Cell>...sourceCells) {
        Map<Cell, BitSet> result = new TreeMap<Cell, BitSet>();
        
        // build list of target cells seen by all source cells
        Set<Cell> targetCells = new LinkedHashSet<Cell>();
        boolean firstCell = true;
        for (Collection<Cell> cells:sourceCells) {
        	for (Cell cell:cells) {
        		if (firstCell) {
                    targetCells.addAll(cell.getHouseCells());
        		}
        		else {
                    targetCells.retainAll(cell.getHouseCells());
        		}
        		firstCell = false;
        	}
        }

        // check if any of the target cells contains value
        BitSet valueBitSet = BitSetFactory.createOneElement(value);
        for (Cell cell:targetCells) {
            if (cell.hasPotentialValue(value))
                result.put(cell, valueBitSet);
        }
        
        return result;
    }
    
	@Override
	public String getProducerName() {
    	return HintResource.getString(R.string.producer_almost_locked_set);
	}
}